import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Huffman {
    class weightComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o2.weight - o1.weight;
        }
    }
    static class Node{
        public int weight;//权重
        public String name;//字符名
        public int left;
        public int right;
        public int parent;
        public String code;//编码
        public int index;
        public Node(String name, int weight) {
            this.name = name;
            this.weight = weight;
            this.left = -1;
            this.right = -1;
            this.parent = -1;
            this.code = "";
            this.index = -1;
        }
    }
    public Node[] arr;//结构数组
    public int leafNum;
    public void create() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        leafNum = n;
        arr = new Node[2*leafNum-1];
        for(int i = 0; i < leafNum; i++){
            in.nextLine();
            String name = in.next();
            int weight = in.nextInt();
            arr[i] = new Node(name, weight);
            arr[i].index = i;
        }
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(new weightComparator());
        for(int i = 0; i < leafNum-1; i++) {
            for(int j = 0; j < leafNum+i; j++) {
                if(arr[j].parent != -1) {
                    continue;
                }
                if(priorityQueue.size() < 2) {
                    priorityQueue.offer(arr[j]);
                    continue;
                }
                Node peek = priorityQueue.peek();
                if(peek.weight > arr[j].weight) {
                    priorityQueue.poll();
                    priorityQueue.offer(arr[j]);
                }
            }
            Node poll1 = priorityQueue.poll();
            Node poll2 = priorityQueue.poll();
            arr[leafNum+i] = new Node("", poll1.weight+poll2.weight);
            arr[leafNum+i].left = poll1.index;
            arr[leafNum+i].right = poll2.index;
            arr[leafNum+i].index = leafNum+i;
            arr[poll1.index].parent = leafNum+i;
            arr[poll2.index].parent = leafNum+i;
        }
    }

    public void print() {
        for (int i = 0; i < 2*leafNum-1; i++) {
            System.out.print(arr[i].name + ": " + arr[i].weight + " ");
        }
        System.out.println();
    }

    public void traverse() {
        int root = 2*leafNum-2;
        preorder(root, "");
    }
    public void preorder(int root, String code) {
        if(root < 0) {
            return;
        }
        arr[root].code = code;
        if(isLeaf(root)) {
            System.out.print(arr[root].name + ":" + arr[root].code + " ");
        }
        if(arr[root].left != -1) {
            preorder(arr[root].left, code+"0");
        }
        if(arr[root].right != -1) {
            preorder(arr[root].right, code+"1");
        }
    }

    private boolean isLeaf(int root) {
        if(arr[root].left == -1 && arr[root].right == -1) {
            return true;
        }
        return false;
    }
    public int WPL;

    public void getWPL() {
        for (int i = 0; i < leafNum; i++) {
            WPL += arr[i].weight*arr[i].code.length();
        }
        System.out.println("WPL:" + WPL);
    }
}
